
{\magonebf 4.7 Persistent Dictionaries (p\_dictionary)}

The difference between dictionaries (cf. section~4.3) and persistent 
dictionaries lies in the fact that update operations performed 
on a persistent dictionary $D$ do not change $D$ but create and return a 
new dictionary $D\'$. For example, $D$.del($k$) returns the dictionary $D\'$ 
containing all items $it$ of $D$ with key($it$) $\ne$ $k$. 

An instance $D$ of the data type $p\_dictionary$ is a set of items (type 
$p\_dic\_item$). Every item in $D$ contains a key from a linearly ordered 
data type $K$, called the key type of $D$, and an information from a data 
type $I$, called the information type  of $D$. The number of items in $D$ 
is called the size of $D$. A dictionary of size zero is called empty. 
We use $<k,i>$ to denote an item with key $k$ and information 
$i$ ($i$ is said to be the information associated with key $k$).  For each 
$k \in K$ there is at most one item $<k,i> \in D$.


\bigskip
{\bf 1. Declaration of a persisten dictionary type}

\decltwo p\_dictionary K I

introduces a new data type with name \name\ consisting of all 
persistent dictionaries with key type $K$ and information type $I$.
\precond $K$ is linearly ordered.

\bigskip
{\bf 2. Creation of a persistent dictionary}


\create D {}

creates an instance \var\ of type \name\ and initializes \var\ to an 
empty persistent dictionary. 


\medskip
{\bf 3. \operations}

\+\cleartabs & \hskip 3.8truecm & \hskip 4truecm &\cr
\+\op K         key {dic\_item\ it}  
                              {returns the key of item $it$.}
\+\nop                        {\precond $it$ $\in$ \var.}
\smallskip
\+\op I         inf {dic\_item\ it}  
                              {returns the information of item $it$.}
\+\nop                        {\precond $it$ $\in$ \var.}
\smallskip
\+\op dic\_item lookup {K\ k} 
                              {returns the item with key $k$ (nil if no such}
\+\nop                        {item exists in \var).}
\smallskip
\+\op I         access {K\ k} 
                              {returns the information associated with $k$}
\+\nop                        {\precond there is an item with key $k$}
\+\nop                        {in \var.}
\smallskip
\+\op p\_dictionary(K,I) del {K\ k}         
                              {returns $\{\ x \in \var\ |\ key(x) \ne k\ \}$.}
\smallskip
\+\op p\_dictionary(K,I) del\_item {dic\_item\ it}    {}
\+\nop                        {returns $\{\ x \in \var\ |\ x \ne it\ \}$.}
\smallskip
\+\op p\_dictionary(K,I) insert {K\ k,\ I\ i} 
                              {returns \var.del($k$) $\cup$ $\{<k,i>\}$.}
\smallskip
\+\op p\_dictionary(K,I) change\_inf {dic\_item\ it,\ I\ i}  {}
\+\nop                        {Let $k = key(it)$, returns \var.del\_item($it$) $\cup$} 
\+\nop                        {$\{<k,i>\}$. \precond $it$ $\in$ \var.}
\smallskip 
\+\op p\_dictionary(K,I) clear {}      
                              {returns an empty persistent dictionary.}
\smallskip
\+\op bool      empty {}      
                              {returns true if \var\ is empty, false otherwise.}
\smallskip 
\+\op int       size {}       
                              {returns the size of \var.}

\medskip
{\bf 4. Iteration}

{\bf forall\_items}($i,D$) 
$\{$ ``the items of $D$ are successively assigned to $i$ '' $\}$


\bigskip
{\bf 5. Implementation}

Persistent Dictionaries are implemented by leaf oriented 
persistent red black trees (cf. [DSST89]).
Operations insert, lookup, del\_item, del take time $O(\log n)$, key, inf, 
empty, size, change\_inf and clear take time $O(1)$. The space requirement is
$O(1)$ for each update operation.
 
%\bigskip
%{\bf 6. Example}
%\medskip
%\input prog/p_dic.prog

